package 复习.面试TOP101.链表;

public class 单链表的排序 {
    public ListNode sortInList (ListNode head) {
        ListNode node = new ListNode(-1);//用来进行已排序节点的构建
        node.next = head;
        ListNode cur = node;
        while(cur.next != null){
            ListNode min = cur.next;
            ListNode premin = cur;
            ListNode res_min = null;
            ListNode res_premin = null;
            while(min != null){
                if(res_min == null || res_min.val > min.val){
                    res_min = min;
                    res_premin = premin;
                }
                min = min.next;
                premin = premin.next;
            }
            res_premin.next = res_min.next;
            res_min.next = cur.next;
            cur.next = res_min;
            cur = cur.next;
        }
        return node.next;
    }
}
/*
// write code here
        ListNode temp = new ListNode(0);
        temp.next = head;
        ListNode key = temp;

        //开始找最小节点
        while(key.next != null){
            ListNode pre = key;
            ListNode cur = key.next;
            ListNode min = null;
            ListNode pre_min = null;
            while(cur != null){
                if(min == null || min.val > cur.val){
                    min = cur;
                    pre_min = pre;
                }
                pre = pre.next;
                cur = cur.next;
            }
            //开始交换
            pre_min.next = min.next;
            min.next = key.next;
            key.next = min;
            key = key.next;
        }

        return temp.next;
 */